/*
 * @Author: lichao 1246877006@qq.com
 * @Date: 2024-09-26 09:55:50
 * @LastEditors: lichao 1246877006@qq.com
 * @LastEditTime: 2024-09-26 15:17:23
 * @FilePath: \algorithm\hello-algo\5 栈与队列\5.3双向队列.js
 * @Description: 这是默认设置,请设置`customMade`, 打开koroFileHeader查看配置 进行设置: https://github.com/OBKoro1/koro1FileHeader/wiki/%E9%85%8D%E7%BD%AE
 */
// 初始化双向队列
const deque = []

// 队尾添加元素
deque.push(1)
deque.push(2)
deque.push(3)

// 队首添加元素
deque.unshift(4)
deque.unshift(5)
deque.unshift(6)

// 访问首元素
const peekFirst = deque[0]
// 访问尾元素
const peekLast = deque[deque.length - 1]

// 元素出队
const popFront = deque.shift()
const popBack = deque.pop()

// 队列的长度
const size = deque.length

// 队列是否为空
const empty = size === 0

// 节点
class Node {
    prev;
    next;
    val;
    constructor(val) {
        this.val = val
        this.next = null
        this.prev = null
    }
}

// 基于双向链表实现双向队列
class LinkedListDequue {
    #front;
    #rear;
    #queSize;

    constructor() {
        this.#front = null
        this.#rear = null
        this.#queSize = 0
    }

    // 获取队列长度
    get size() {
        return this.#queSize
    }

    // 是否为空
    isEmpty() {
        return this.size === 0
    }

    // 队尾入队
    pushLast(val) {
        const node = new Node(val)
        if(this.size === 0) {
            // 没有节点
            this.#front = node
            this.#rear = node
        } else {
            // 有节点
            // 更新当前尾节点的 next
            this.#rear.next = node
            // 将插入的节点关联之前的尾节点
            node.prev = this.#rear
            // 更新尾节点
            this.#rear = node
        }
        this.#queSize++
    }

    // 队首入队
    pushFirst(val) {
        const node = new Node(val)
        if(this.size === 0) {
            this.#front = node
            this.#rear = node
        } else {
            // 更新当前首节点的 prev
            this.#front.prev = node
            // 将插入的节点的 next 绑定旧首节点
            node.next = this.#front
            // 更新首节点
            this.#front = node
        }
        this.#queSize++
    }

    // 队尾出队
    popLast() {
        if(this.isEmpty()) return null
        // 获取尾节点的 val
        const value = this.#rear.val
        // 获取当前尾节点之前的节点
        const prev = this.#rear.prev
        if(prev != null) {
            // 更新尾节点之前节点的 next
            prev.next = null
            // 更新当前尾节点的 prev
            this.#rear.prev = null
        }
        // 更新尾节点
        this.#rear = prev
        this.#queSize--
        return value
    }

    // 队首出队
    popFirst() {
        if(this.isEmpty()) return null
        // 获取当前首节点的 val
        const value = this.#front.val
        // 获取当前首节点之后的节点
        const next = this.#front.next
        if(next !== null) {
            // 更新首节点之后节点的 prev
            next.prev = null
            // 更新当前首节点的 next
            this.#front.next = null
        }
        // 更新首节点
        this.#front = next
        this.#queSize--
        return value
    }

    // 访问队首元素
    peekFirst() {
        return this.isEmpty() ? null : this.#front.val
    }

    // 访问队尾元素
    peekLast() {
        return this.isEmpty() ? null : this.#rear.val
    }

    // 打印双向队列
    print() {
        const arr = []
        let temp = this.#front
        while(temp !== null) {
            arr.push(temp.val)
            temp = temp.next
        }
        console.log(`[${arr.join(',')}]`)
    }
}

// 基于数组实现双向队列
class ArrayDeque {
    #nums;
    #front;
    #queSize;

    constructor(capacity) {
        this.#nums = new Array(capacity)
        this.#front = 0
        this.#queSize = 0
    }

    // 获取队列的容量
    get capacity() {
        return this.#nums.length
    }

    // 获取双向队列的长度
    get size() {
        return this.#queSize
    }

    // 队列是否为空
    get isEmpty() {
        return this.size === 0
    }

    // 计算数组索引
    index(i) {
        // 通过区域操作实现数组首位相连
        // 当 i 越过数组尾部后,回到头部
        // 当 i 越过数组头部后,返回尾部
        return (i + this.capacity) % this.capacity
    }

    // 队首入队
    pushFirst(val) {
        if(this.size === this.capacity) {
            throw new Error('队列满')
        }
        // 队首指针向左移动一位
        // 通过取余操作实现 front 越过数组头部后回到尾部
        this.#front = this.index(this.#front - 1)
        this.#nums[this.#front] = val
        // 更新队列长度
        this.#queSize++
    }

    // 队尾入队
    pushLast(val) {
        if(this.size === this.capacity) {
            throw new Error('队列满')
        }
        // 计算队尾指针,指向队尾索引 + 1
        const rear = this.index(this.#front + this.size)
        this.#nums[rear] = val
        this.#queSize++
    }

    // 访问队首
    peekFirst() {
        if(this.isEmpty) throw new Error('队列为空')
        return this.#nums[this.#front]
    }

    // 访问队尾
    peekLast() {
        if(this.isEmpty) throw new Error('队列为空')
        const last = this.index(this.#front + this.size - 1)
        return this.#nums[last]
    }

    // 队首出队
    popFirst() {
        const num = this.peekFirst()
        this.#front = this.index(this.#front + 1)
        this.#queSize--
        return num
    }

    // 队尾出队
    popLast() {
        const num = this.peekLast()
        this.#queSize--
        return num
    }

    toArray() {
        const res = []
        for(let i = 0, j = this.#front; i < this.size; i++, j++) {
            res[i] = this.#nums[this.index(j)]
        }
        return res
    }
}

